import { LinkedList, Node } from './linked_list.js'

class DoublyNode extends Node {
    constructor(element) {
        super(element)
        this.prev = null
    }
}

export class DoublyLinkedList extends LinkedList {
    constructor() {
        super()
        this.tail = null
    }
    // 追加
    append(element) {
        const newNode = new DoublyNode(element)
        // 是否为空
        if (!this.head) {
            this.head = newNode
            this.tail = newNode
        } else {
            // 找到最后一个节点
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        }
        this.length++
    }
    // 正向遍历
    forwardString() {
        let current = this.head
        let forwardStr = ""

        while (current) {
            forwardStr += "<-->" + current.element
            current = current.next
        }

        return forwardStr.slice(4)
    }
    // 反向遍历
    reverseString() {
        var current = this.tail
        var reverseStr = ""

        while (current) {
            reverseStr += "<-->" + current.element
            current = current.prev
        }

        return reverseStr.slice(4)
    }
    // 插入
    insert(position, element) {
        if (position < 0 || position > this.length) {
            return false
        }
        const newNode = new DoublyNode(element)
        // 判断多种插入情况
        if (position === 0) {
            if (this.head === null) {
                this.head = newNode
                this.tail = newNode
            } else {
                newNode.next = this.head
                this.head.prev = newNode
                this.head = newNode
            }
        } else if (position === this.length) {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        } else {
            // 中间插入
            let index = 0
            let current = this.head
            let previous = null
            while (index++ < position) {
                previous = current
                current = current.next
            }
            previous.next = newNode
            newNode.previous = previous
            newNode.next = current
            current.previous = newNode
        }
        this.length++
        return true
    }
    // get
    // indexOf
    // removeAt
    removeAt(position) {
        if (position < 0 || position > this.length - 1) {
            return null
        }
        let current = this.head
        if (position === 0) {
            if (this.length === 1) {
                this.head = null
                this.tail = null
            } else {
                this.head = this.head.next
                this.head.prev = null
            }
        } else if (position === this.length - 1) {
            this.tail.prev.next = null
            this.tail = this.tail.prev
            current = this.tail
        } else {
            let index = 0
            let previous = null
            while (index++ < position) {
                previous = current
                current = current.next
            }
            previous.next = current.next
            current.next.prev = previous
        }
        return current.element
    }
    // update
    // remove
}